package 剑指offer;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;


public class _38字符串的排列 {
	
	List<String> list =new ArrayList<>();
	char []c;
    public String[] permutation(String s) {
    	c=s.toCharArray();
    	dfs(0);
    		
		
		 return list.toArray(new String[list.size()]);
    }
    public void dfs(int i) {
    	if(i==c.length-1) {
    		list.add(new String(c));
    		return;
    	}
    	HashSet<Character> set =new HashSet<Character>();
    	for (int j = i; j < c.length; j++) {
			if(set.contains(c[j])) continue;
			set.add(c[j]);
			swap(j, i);
			dfs(i+1);
			swap(i, j);
    	}
    	 	 
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }

}
